package pers.qianyu.month_202102.date_20210221;

import java.util.*;

/**
 * 1438. 绝对差不超过限制的最长连续子数组
 * https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
 * - 本质就在于找到窗口中的最大值和最小值
 *
 * @author mizzle rain
 * @date 2021-02-21 15:13
 */
public class LongestSubarray {
    // 使用优先队列
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int res = 0;
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        for (int left = 0, right = 0; right < n; right++) {
            maxQueue.offer(nums[right]);
            minQueue.offer(nums[right]);
            while (maxQueue.peek() - minQueue.peek() > limit) {
                maxQueue.remove(nums[left]);
                minQueue.remove(nums[left]);
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    // 使用平衡树
    public int longestSubarray2(int[] nums, int limit) {
        int n = nums.length;
        int res = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int left = 0, right = 0; right < n; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            while (map.lastKey() - map.firstKey() > limit) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    // 使用单调队列
    public int longestSubarray3(int[] nums, int limit) {
        Deque<Integer> minQueue = new ArrayDeque<>();
        Deque<Integer> maxQueue = new ArrayDeque<>();
        int n = nums.length;
        int res = 0;
        for (int left = 0, right = 0; right < n; right++) {
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[right]) maxQueue.removeLast();
            maxQueue.addLast(nums[right]);
            while (!minQueue.isEmpty() && minQueue.peekLast() > nums[right]) minQueue.removeLast();
            minQueue.addLast(nums[right]);
            while (!maxQueue.isEmpty() && !minQueue.isEmpty() && maxQueue.peekFirst() - minQueue.peekFirst() > limit) {
                if (maxQueue.peekFirst() == nums[left]) maxQueue.removeFirst();
                if (minQueue.peekFirst() == nums[left]) minQueue.removeFirst();
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
